// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2002 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: stst.h,v 1.8 2010-03-11 15:16:45 carzanig Exp $
//
#ifndef SIENA_STST_H
#define SIENA_STST_H

#include <cassert>
#include "allocator.h"

namespace siena {

//
// the basic TST algorithms are taken more or less directly from
// R. Sedgewick's "Algorithms in C" 3rd Ed. pp 638--639.
//

/** @brief a node in a simple ternary search trie (STST) **/
class STSTNode {
public:
    void *		data;

    STSTNode(int xc) throw() 
	: data(0), c(xc), left(0), middle(0), right(0) {};

private:
    int			c;
    STSTNode *		left;
    STSTNode *		middle;
    STSTNode *		right;

    friend class STST;
};

/** @brief a classic ternary search tree for strings.
 *
 *  This data structure is taken more or less directly from
 *  R. Sedgewick's "Algorithms in C" 3rd Ed. pp 638--639.
 **/
class STST {
public:
			STST() throw() { clear(); };

    STSTNode *		insert(const char *, const char *, 
			       FTAllocator &) throw();
    const STSTNode *	find(const char *, const char *) const throw();

    void		clear() throw();

    static const int	EndChar = -1;

private:
    STSTNode *		roots[256];
};

} // end namespace siena

#endif
